package leetcode;

/**
 * Created by Ghost on 2015/2/3.
 */
public class Gas_Station {

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int begin=0,end=0;
        int count= gas.length;
        int n=0;
        int left = 0;
        int current = begin;
        while(n<count){
            left += gas[current]-cost[current];
            if(left>=0){
                end++;
                current=end;
            }
            else{
                begin--;
                if(begin<0)
                    begin=count-1;
                current = begin;
            }
            n++;
        }

        if(left>=0)
            return begin;
        else
            return -1;

    }

    public static void main(String[] args){
        Gas_Station gas_station = new Gas_Station();
        int[] gas = {1,2,3,1,1,2};
        int[] cost = {1,1,2,1,3,3};
        System.out.println(gas_station.canCompleteCircuit(gas,cost));
    }
}
